\begin{frame}[allowframebreaks]
\frametitle{Finite Matrix Automata}

\begin{define}[FSMA \cite{giftsironmoneyranisironmoney1972abstract}]

A finite state matrix automaton is a
9-tuple $M~=~(Z,~\Sigma,~T,~\delta,~\delta',~I,~E,~E',~$\$$)$, where

\begin{itemize}
	\item $Z = \bar{Z} \cup Z_1 \cup \ldots \cup Z_k, Z_i \cap Z_j = \emptyset, i
		\not= j,$ is a finite set of states. Each $Z_i$ has an initial state $z_{0_i}$
		and a final state $z_{e_i}$. $\bar{Z}$ has an initial state $z_0$
	\item $\Sigma$ is a finite set of input symbols
	\item T is a finite set of stack symbols, $\left| T \right| = k$
	\item $I = \{z_{0_1}, \ldots, z_{0_k}\}$ is the set of initial states
	\item $E \subseteq \bar{Z}$ is the set of final states
	\item $E' = \{z_{e_1}, \ldots, z_{e_k}\}$ is the set of transition states
\end{itemize}

\end{define}

\begin{define}[FSMA \cite{giftsironmoneyranisironmoney1972abstract}]

\begin{itemize}
  \item \$$ \text{ }\not\in \Sigma$ is the endmarker
  \item $\delta: Z_i \times \Sigma \rightarrow Z_i \times \{\epsilon\}$,
  $z_{e_i} \times$ \$ $\rightarrow (\text{I }\cup \{z_0\}) \times s_i$ where
  $s_i$ is the stack symbol corresponding to $Z_i, i = 1, \ldots, k$
  \item $\delta': \bar{Z} \times T \rightarrow \bar{Z}$ 
\end{itemize}

\end{define}

\end{frame}

\begin{frame}
\frametitle{Finite Matrix Automata Languages}

\begin{define}[\cite{giftsironmoneyranisironmoney1972abstract}]

If M is a FSMA, then 
\begin{align*} L(M) = \{[a_{ij}], i = 1, \dots m, j = 1, \dots, n, m, n \geq 1
\vert a_{ij} \in \Sigma \text{ such that }\\
(z, (1, 1), \epsilon, 1) \overset{*}{\underset{\delta}{\vdash}} (z_0,(m + 1, n),
y, 1) \overset{*}{\underset{\delta'}{\vdash}} (z',(m + 1, n), y, n)\\ \text{
with } z \in I, z' \in E \text{ and } y \in T^+\}\end{align*}

is called the accepted language of M.

\end{define}

The 4-tupel $(z, (i, j), y, r)$ describes a configuration of M where $z$ is the
current state, $(i, j)$ the position of the input pointer, $y$ the string of the
storage tape and $r$ the number of cells from the left end of the position of
the storage pointer.

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Example}

\begin{Example}
$M~=~(Z,~\{., X\},~\{T_1, T_2\},~\delta,~\delta',~\{z_{0_1}, z_{0_2}\},~\{z_e\},~\{z_{e_1}, z_{e_2}\},~$\$$)$ is a FSMA where
\begin{itemize}
	\item $Z = \bar{Z} \cup Z_1 \cup Z_2$, $\bar{Z} = \{z_0, z_1, z_e\}, Z_1 =
	\{z_{0_1}, z_{e_1}\}, Z_2 = \{z_{0_2}, z_{e_2}\}$
	\item $\delta(z_{0_1}, X) = \{(z_{0_1}, \epsilon), (z_{e_1}, \epsilon)\}$
	\item $\delta(z_{0_2}, X) = \{(z_{e_2}, \epsilon)\}, \delta(z_{0_2}, .) =
	\{(z_{0_2}, \epsilon)\}$
	\item $\delta(z_{e_1}, $\$$) = \{(z_{0_1}, T_1), (z_{0_2}, T_1), (z_{0},
	T_1)\}$
	\item $\delta(z_{e_2}, $\$$) = \{(z_{0_1}, T_2), (z_{0_2}, T_2), (z_{0},
	T_2)\}$
	\item $\delta'(z_{0}, T_1) = \delta'(z_{1}, T_2) = z_{1}, \delta'(z_{1}, T_1) =
	z_e$
\end{itemize}
\end{Example}


L(M) describes Pictures containing token U of x's with .'s in between of
different size and proportion.


\end{frame}

\begin{frame}
\frametitle{Example configuration steps}

\[
\boxed{
\begin{aligned}
\begin{matrix}
z_{0_1}X & . & . & X \\[-0.5ex]
X & . & . & X \\[-0.5ex]
X & X & X & X \\[-0.5ex] 
*\$ & \$ & \$ & \$
\end{matrix}
\end{aligned}
}
\overset{*}{\underset{\delta}{\vdash}}
\boxed{
\begin{aligned}
\begin{matrix}
 & . & . & X \\[-0.5ex]
 & . & . & X \\[-0.5ex]
z_{0_1}X & X & X & X \\[-0.5ex] 
*\$ & \$ & \$ & \$
\end{matrix}
\end{aligned}
}
\underset{\delta}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
 & . & . & X \\[-0.5ex]
 & . & . & X \\[-0.5ex]
 & X & X & X \\[-0.5ex] 
z_{e_1}*\$ & \$ & \$ & \$
\end{matrix}
\end{aligned}
}
\]

\[
\underset{\delta}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
 & z_{0_2}. & . & X \\[-0.5ex]
 & . & . & X \\[-0.5ex]
 & X & X & X \\[-0.5ex] 
T_1 & *\$ & \$ & \$
\end{matrix}
\end{aligned}
}
\overset{*}{\underset{\delta}{\vdash}}
\boxed{
\begin{aligned}
\begin{matrix}
 &  &  &  \\[-0.5ex]
 &  &  &  \\[-0.5ex]
 &  &  &  \\[-0.5ex] 
T_1 & T_2 & T_2 & z_{e_1}*\$
\end{matrix}
\end{aligned}
}
\underset{\delta}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
z_0*T_1 & T_2 & T_2 & T_1
\end{matrix}
\end{aligned}
}
\]

\[
\underset{\delta'}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
T_1 & z_1*T_2 & T_2 & T_1
\end{matrix}
\end{aligned}
}
\overset{*}{\underset{\delta'}{\vdash}}
\boxed{
\begin{aligned}
\begin{matrix}
T_1 & T_2 & T_2 & z_1*T_1
\end{matrix}
\end{aligned}
}
\underset{\delta'}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
T_1 & T_2 & T_2 & z_e*T_1
\end{matrix}
\end{aligned}
}
\]

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[allowframebreaks]
\frametitle{Pushdown Matrix Automata}

\begin{define}[PDMA \cite{giftsironmoneyranisironmoney1972abstract}]

A pushdown matrix automaton is a
11-tuple $M~=~(Z,~\Sigma,~T_1,~T_2,~\delta,~\delta',~I,~E,~E',Z_0,~$\$$)$, where

\begin{itemize}
	\item $Z = \bar{Z} \cup Z_1 \cup \ldots \cup Z_k, Z_i \cap Z_j = \emptyset, i
		\not= j,$ is a finite set of states. Each $Z_i$ has an initial state $z_{0_i}$
		and a final state $z_{e_i}$. $\bar{Z}$ has an initial state $z_0$
	\item $\Sigma$ is a finite set of input symbols
	\item $T_1$ is the finite set of first storage symbols, $\left| T_1 \right| =
	k$
	\item $T_2$ is the finite set of second  storage symbols 
	\item $I = \{z_{0_1}, \ldots, z_{0_k}\}$ is the set of initial states
	\item $E \subseteq \bar{Z}$ is the set of final states
\end{itemize}

\end{define}

\begin{define}[PDMA \cite{giftsironmoneyranisironmoney1972abstract}]

\begin{itemize}
  \item $E' = \{z_{e_1}, \ldots, z_{e_k}\}$ is the set of transition states
  \item $Z_0 \in T_2$ is the initial symbol of the second storage
  \item \$$ \text{ }\not\in \Sigma$ is the endmarker
  \item $\delta: Z_i \times \Sigma \rightarrow Z_i \times \{\epsilon\}$,
  $z_{e_i} \times $\$ $\rightarrow (\text{I }\cup \{z_0\}) \times s_i$ where
  $s_i \in T_1$ corresponding to $Z_i, i = 1, \ldots, k$
  \item $\delta': \bar{Z} \times (T_1 \cup \{\epsilon\}) \times T_2 \rightarrow
  \bar{Z} \times T_2^*$
\end{itemize}

\end{define}

\end{frame}

\begin{frame}
\frametitle{Matrix automata and matrix languages}

\begin{thm}
FSMA are equivalent to RML,
PDMA are equivalent to CFML, 
Linear bounded matrix automata are equivalent to CSML and
Turing machine matrix automata are equivalent to PSML.
\end{thm}

\begin{proof}
Can be seen in \cite{giftsironmoneyranisironmoney1972abstract}. It will be shown
that every language that are derivated by right linear matrix grammar can be
accepted by a finite state matrix automata and vice versa. The other
equivalences can be shown equivalent.
\end{proof}

\end{frame}